부산대학교자료구조
Scientific Inference Lab

When Do We Visit the Root

Level Order Traversal

레벨 순회(level order traversal)는 루트에서 가까운 노드를 먼저 방문하는 트리 순회다. 큐에서 꺼낸 노드를 방문하고 그 자식 노드를 뒤쪽에 넣으므로, 먼저 넣은 얕은 노드가 더 깊은 노드보다 먼저 나온다.

큐 하나루트를 넣고, 꺼낸 노드를 방문한 뒤 자식 노드를 넣기를 큐가 빌 때까지 반복한다.
깊이 순서출력에서 깊이가 줄어드는 일은 없다.
넣는 순서같은 깊이 안의 좌우 순서는 자식 노드를 큐에 넣은 순서를 따른다.

큐에서 꺼낸 노드를 방문하고 그 자식 노드를 뒤에 넣는다

queue = deque([A])에서 시작한다. 꺼낸 횟수를 옮기면 방문한 노드, 새로 넣은 자식 노드, 큐의 앞쪽에서 뒤쪽까지의 내용이 바뀐다.

레벨 순회의 큐방문한 노드와 큐
가로 띠 하나가 같은 깊이의 층이다. 초록으로 채운 원이 방금 꺼내 방문한 노드, 옅은 파란 원이 이미 방문한 노드, 점선 테두리 원이 큐에서 기다리는 노드이고 원 옆 수가 방문 순서다. 아래 줄은 왼쪽이 앞쪽인 큐이며 초록 테두리 칸이 방금 넣은 자식 노드다.

자식 노드를 넣는 순서가 같은 깊이 안의 좌우 순서를 정한다

자식 노드를 큐에 넣는 순서를 바꾸면 깊이별 방문 순서가 바뀐다. 어느 순서로 넣어도 얕은 층이 깊은 층보다 먼저 나온다.

행은 깊이다. 칸의 수는 전체 방문 순서에서 그 노드가 나온 번째다.

같은 절차에서 큐를 스택으로 바꾸면 한 갈래를 끝까지 먼저 내려간다

꺼낸 노드를 방문하고 왼쪽, 오른쪽 자식 노드를 차례로 넣는 절차는 그대로 두고 대기 공간만 바꾸면 방문 순서와 깊이의 변화가 바뀐다.

큐와 스택의 방문 순서방문 순서와 각 노드의 깊이
칸 하나가 방문 하나이고 왼쪽부터 방문 순서다. 칸 아래 수는 그 노드의 깊이이며, 빨간 수는 앞 방문보다 깊이가 줄어든 곳이다.